package com.sise.Tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 *      二叉搜索树的 前中后序遍历
 */
public class Traversal {

    /**
     * 前序遍历 : 根左右
     */
    public void preOrderTraversal(TreeNode root){
        if (root == null) return;
        System.out.println(root.val);
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }

    /**
     * 中序遍历 : 左根右
     */
    public void inOrderTraversal(TreeNode root){
        if (root == null) return;
        inOrderTraversal(root.left);
        System.out.println(root.val);
        inOrderTraversal(root.right);
    }

    /**
     * 后序遍历 : 左右根
     */
    public void postOrderTraversal(TreeNode root){
        if (root == null) return;
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.println(root.val);
    }

    /**
     * 层次遍历 - BFS
     */
    public void levelOrderTraversal(TreeNode root){
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            TreeNode poll = queue.poll();
            System.out.println(poll.val);

            if (root.left != null){
                queue.offer(root.left);
            }
            if (root.right != null){
                queue.offer(root.right);
            }
        }
    }

    /**
     *  前序遍历 - 迭代
     */


}
